mergeQueue = []
def mergeSort(lst, low, high):
    global mergeQueue
    if high - low < 2:
        mergeQueue.append([low, high])
        return

    mid = (low + high) // 2

    mergeSort(lst, low, mid)
    mergeSort(lst, mid, high)
    lo, hi = merge(lst, low, mid, high)
    mergeQueue.append([lo, hi])

def merge(lst, low, mid, high):
    i = low
    j = mid
    lstm = []
    while i < mid and j < high:
        if lst[i] < lst[j]:
            lstm.append(lst[i])
            i += 1
        else:
            lstm.append(lst[j])
            j += 1
    
    while i < mid:
        lstm.append(lst[i])
        i += 1
 
    while j < high:
        lstm.append(lst[j])
        j += 1

    lst[low: high] = lstm
    return low, high

a = [100, 200, 120, 80, 50, 150, 20, 160, 90, 130, 190]
b = a[:]

mergeSort(a, 0, len(a))
print(a)
print('-------------------')
print(mergeQueue)
print('-------------------')
sortStack = []
lastSpace = 1

for i in range(len(mergeQueue)):
    curSpace = mergeQueue[i][1] - mergeQueue[i][0]

    if curSpace > lastSpace:
        n = len(sortStack)
        aa = sortStack[n - 2]
        bb = sortStack[n - 1]
        merge(b, aa[0], bb[0], bb[1])
        sortStack.pop()
        sortStack.pop()

    sortStack.append(mergeQueue[i])
    lastSpace = curSpace
    
print(b)

